Міністерство освіти і науки України
Національний університет
«Львівська політехніка»
кафедра САПР
Лабораторна робота №3
з курсу “Основи проектування систем штучного інтелекту”
тема: АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ.
Виконав:
cт. гр. КН-3
Львів-2008
1.Мета роботи
Вивчити принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
2. Короткі теоретичні відомості
2.1. Алгоритм k-внутрішніх групових середніх розпізнавання образів
КРОК 1.
Вибираються к початкових центрiв кластерiв Z1(1), Z2(1),...,Zk(1).
Цей вибір здiйснюється довiльно i, звичайно, в якостi початкових центрiв використовуються першi k результатiв вибiрки з заданої множини образiв.
КРОК 2.
На k-му кроцi iтерацiї задана множина образiв розподiляється по k кластерах за таким правилом : XєSj(k), якщо ||X-Zj(k)||<=||X-Zj(k)||, для всiх i=1,2,...,k, ij, де Sj(k) - множина образiв, якi входять в кластер з центром Zj(k). У випадку рiвностi рiшення приймаються довiльним чином.
КРОК 3.
На основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, виходячи з умови, що сума квадратiв вiдстаней мiж усiма образами, що належать множині Sj(k), i новiм центром кластера повинна бути мiнiмальною. Iншими словами, новi центри кластерiв Zj(k+1) вибираються таким чином, щоб мiнiмiзувати показник якостi
Jj=||X-Zj(k+1)||^2, j=1,2,...,k. XєSj(k)
Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k). Вiдповiдно, новi центри кластерiв визначаються як:
Zj(k+1)=(1/Nj)X, j=1,2,...,k, XЄSj(k),
де Nj- число вибiркових образiв, що входять в множину типу Sj(k).
Очевидно, що назва алгоритму "К внутрiшнiх групових" визначається способом, прийнятим для послiдовної корекцiї призначення центрiв кластерiв.
КРОК 4.
Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Iнакше, крок 2. Якiсть залежить:
вiд кiлькостi вибираємих центрiв кластерiв;
вiд вибору початкових центрiв кластерiв;
вiд послiдовностi проглядання образiв;
вiд геометричної особливостi даних.
Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерiв.
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
4.6. Х1(0,3), Х2(0,5), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(10,10), Х13(20,8), Х14(20,9). K=4
Текст програми:
Program Laba_1;
Uses CRT;
const q = 14 ; kl = 4;
type dis = record
v:array [1..q] of real;
t:array [1..q] of integer;
end;
var
x : array [1..q] of integer;
y : array [1..q] of integer;
j,i,k:integer;
d: array [1..kl] of dis;
serx,sery:real;
centre: array [1..kl] of integer;
centrex: array [1..kl] of real;
centrey: array [1..kl] of real;
cx: array [1..kl] of real;
cy: array [1..kl] of real;
min:real; ok:boolean;
Label next,quit;
BEGIN
clrscr;writeln;
x[1]:= 0 ; y[1]:=3;
x[2]:= 0 ; y[2]:=5;
x[3]:= 0 ; y[3]:=6;
x[4]:= 1 ; y[4]:=4;
x[5]:= 5 ; y[5]:=0;
x[6]:= 6 ; y[6]:=0;
x[7]:= 7 ; y[7]:=0;
x[8]:= 6 ; y[8]:=1;
x[9]:= 5 ; y[9]:=5;
x[10]:=6 ; y[10]:=6;
x[11]:=7 ; y[11]:=7;
x[12]:=10; y[12]:=10;
x[13]:=20; y[13]:=8;
x[14]:=20; y[14]:=9;
textcolor(8);
writeln(' (C) Copyright Demon KN-316/L3-v:18. 2008 ');
writeln; writeln; textcolor(15);
For i:=1 to kl do begin
centre[i]:=i; centrex[i]:=x[i]; centrey[i]:=y[i];
writeln(' CENTRE ',i,' --- Z',i,'(',centrex[i]:1:1,';',centrey[i]:1:1,');');
end;
NEXT:;
writeln; readln; textcolor(14);
write(' Z1(',centrex[1]:1:1,';',centrey[1]:1:1,') ');
For i:=2 to kl do
if i=kl then writeln('Z',i,'(',centrex[i]:1:1,';',centrey[i]:1:1,')') else
write('Z',i,'(',centrex[i]:1:1,';',centrey[i]:1:1,')',' ');
...
